#include<iostream>

typedef struct node{
    int data;
    struct node *next;
}NODE;

//要实现的函数
/**
 * 
 * 时间复杂度为：O(n)，实际上是三次O(n)
 * @param head 带有头节点的链表
 * 
 */
void reorder(NODE* head){
    if(head->next==nullptr) return;
    NODE *first=head->next;
    NODE* second=head->next;
    while (second!=nullptr&&second->next!=nullptr)
    {
        first=first->next;
        second=second->next->next;
    }
    //此时fist节点节点就是第一段的最后一个节点
    //得到第二段的头，然后断开两端
    NODE* curr=first->next;
    NODE* pre=nullptr;//这样的单个节点可以随便写，不增加时间复杂度的
    first->next=nullptr;
    //将后面的反转，然后连接到fist上
    while (curr!=nullptr)
    {
        NODE* temp=curr->next;
        curr->next=pre;
        pre=curr;
        curr=temp;
    }
    //反转完毕，开始遍历两个链表
    NODE* head1=head->next;
    NODE* head2=pre;
    //使用一个新的头搞也可以
    while (head1!=nullptr&&head2!=nullptr)
    {
        auto temp1=head1->next;
        auto temp2=head2->next;
        head1->next=head2;
        head1=temp1;
        head2->next=temp1;
        head2=temp2;
    }  

}
#include<iostream>
#include<vector>
using namespace std;
void showNode(NODE* head){
    auto temp=head->next;
    while (temp!=nullptr)
    {
        cout<<temp->data <<" "<<endl;
        temp=temp->next;
    }
    cout<<endl;
}
/**
 * 初始化链表
 */
void initList(NODE* head, vector<int> arr){
    auto tail=head;
    for(auto var : arr){
        auto temp=new NODE();
        temp->data=var;
        temp->next=nullptr;
        tail->next=temp;
        tail=tail->next;
    }
}
int main(void){
    NODE* head=new NODE();
    head->data=0;
    head->next=nullptr;

    vector<int> arr={};
    initList(head,arr);
    showNode(head);
    reorder(head);
    showNode(head);
    return 0;
}